package com.xigua._搜索或回溯算法;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格
 * （不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，
 * 当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，
 * 因为3+5+3+8=19。请问该机器人能够到达多少个格子？
 *
 * @date 2022/3/1923:22
 */
public class _剑指Offer13_机器人的运动范围 {


    public static void main(String[] args) {
        movingCount(1,2,1);
    }

    public static int movingCount(int m, int n, int k) {
        boolean board[][] = new boolean[m][n];
        return  dfs(0,0,board,k);
    }

    private static int dfs(int a,int b,boolean [][]board, int k) {
        if (a<0 || a>=board.length || b<0 ||b>= board[0].length || sumUnit(a)+sumUnit(b)>k || board[a][b] == true )return 0;
        board[a][b] = true;
        return 1+dfs(a+1,b,board,k)+dfs(a-1,b,board,k)+dfs(a,b+1,board,k)+dfs(a,b-1,board,k);
    }

    static int sumUnit(int a){
        int sum = 0;
        while (a>=10){
            sum += a%10;
            a = a/10;
        }
        return sum+a;
    }

}
